package org.nowcoder.leetcode.BSearch;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Title  : 658. Find K Closest Elements
 * Source : https://leetcode.cn/problems/find-k-closest-elements/
 * Author : XrazYang
 * Date   : 2024-04-29
 */

public class LeetCode_658 {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int index = binarySearch0(arr, x);
        List<Integer> results = new ArrayList<>();
        int count = 0;
        int l = index - 1, r = index;
        while (count < k) {
            if (l >= 0 && r < arr.length) {
                int var0 = x - arr[l];
                int var1 = arr[r] - x;
                if (var0 <= var1) {
                    results.add(arr[l--]);
                } else {
                    results.add(arr[r++]);
                }
                count++;
            } else if (l < 0) {
                for (int i = r; i < r + (k - count); i++) {
                    results.add(arr[i]);
                }
                break;
            } else {
                for (int i = l; i > l - (k - count); i--) {
                    results.add(arr[i]);
                }
                break;
            }
        }
        Collections.sort(results);
        return results;
    }

    private int binarySearch0(int[] arr, int x) {
        int l = 0, r = arr.length;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (arr[mid] < x) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
}
